其他
超越数学的判定——通用图灵机的诞生
点击上方蓝字“返朴”进入主页，可关注查阅往期文章
1900年，伟大的数学家希尔伯特提出了23个问题，他希望将整个数学体系建立在坚实的基础上，呐喊出了“我们必须知道，我们必将知道”。但哥德尔不完备性定理的提出将其梦碎，数学的一致性和完备性不可同时存在。英国数学家、计算机先驱图灵进一步对数学的判定问题做出了结论——通过通用图灵机在有限推理内可以解决的即是可判定问题，反之则不可判定。而通用图灵机的诞生不仅证明了数学的不完美，由此发明的通用计算机完全改变了世界。“人类的思维永远无法被机器所取代”，但人类会因有机器探索更远的思想边界。
那是剑桥大学1935年的四旬节学期（译者注：复活节前的六周禁食期，也是剑桥大学冬季学期的名称。），正值暮冬时分。在暗淡的灰色光线中，剑桥大学古老的尖塔和围墙环绕的学院更显年代感。在英国的这个潮湿而寒冷的角落里，尽管冬天异常温暖，但天气依然是阴沉沉的。在剑桥大学圣约翰学院旁边的院子里，钟楼上的三一钟在上午10点响起了刺耳的钟声——10下惊心动魄的钟声接连10下更高音调的钟声，诗人华兹华斯（Wordsworth）曾把三一钟的钟声比作“女性”的声音。圣约翰学院位于狭窄的中世纪老式街道上，距离国王学院不远，据说是剑桥大学第二富有的学院，仅次于最富有的三一学院。有一个流传了几个世纪的传言，说从剑桥大学圣约翰学院一直走到遥远的牛津大学圣约翰学院，都不用踏出圣约翰的土地。马克斯·纽曼是圣约翰学院的一名研究员，他大步走进了教室。戴着眼镜，秃头，年近40岁的纽曼，是英国数学界冉冉升起的新星。走路的时候，身上的学位服会随着他的步伐不断摆动。教室已经有几个世纪的历史了，给人的感觉好像是一座古老的大教堂或修道院的一部分。纽曼教授的课程“数学基本原理”以难度大而著称，所以教室里的学生并不多。图灵正专心致志地坐在讲台下。
1931年艾伦·图灵（后排右三）在剑桥国王学院的合影丨图片来源：Cambridge
该系列课程的“压轴戏”是阐述库尔特·哥德尔（Kurt Gödel）取得的一些惊人成果。哥德尔是维也纳大学一名25岁的数学家，生性沉默寡言，但非常聪明。1940年，哥德尔逃离了纳粹统治下的维也纳来到美国——纳粹不顾他患有各种真实的或是编造的疾病，要求他参军，但他宁愿成为难民也不参军。潜伏在德国潜艇中横渡大西洋的风险太大，所以哥德尔沿着苏联的西伯利亚大铁路一路向东，然后乘船从日本逃到旧金山。他被普林斯顿高等研究所录取，那里已经聚集了一批欧洲最伟大的科学家和数学家，其中包括阿尔伯特·爱因斯坦和约翰·冯·诺伊曼，诺伊曼在之后曾深度参与洛斯阿拉莫斯（Los Alamos）原子弹计划。
1931年，哥德尔证明了算术系统的不完备性，这一惊人而又奇特的结论将是纽曼最后几节课的主题。哥德尔的成果被称为“哥德尔不完备性定理”，至今仍是数学领域最令人震惊的发现之一。哥德尔不完备性定理表明，无论算术系统的形式规则是如何制定的，总会有一些算术公理无法通过规则来证明，就如简单的皮亚诺算术系统中的关系式2+2=4。这给人的感觉有点儿像制造出来的拼图故意少了一些碎片，或者新地毯永远无法完美覆盖到房间的四个角落。消除不完备性的唯一方法似乎是重置规则，使其前后自相矛盾，但这似乎并不是一个完美的解决方案。
哥德尔指出，数学中有些真实性无法被证明。这个结论令人震惊，甚至激怒了一些人。数学家不仅倾向于认为所有真实的事物都可以被证明，而且认为所有重要的事物都应该能够被证明，因为只有通过清晰的、规则明确的严格证明才能带来确定性。纽曼计划在未来几周的时间里来讲述这个令人敬畏的主题，在当天的演讲中，他谈论的不是哥德尔，而是德国哥廷根大学的著名数学教授希尔伯特（David Hilbert）。希尔伯特比哥德尔年长40多岁，实际上他被誉为欧洲数学界的教皇。在数学领域，希尔伯特有句名言：“我们必须知道，我们必将知道。”1900年，在巴黎国际数学大会的演讲中，希尔伯特向国际数学界提出了23个有待解决的数学难题，这为20世纪的数学发展制订了计划。而图灵，一个颇有些愤世嫉俗的剑桥研究生，将证明希尔伯特的部分观点从根本上就是错的。
纽曼正在向学生介绍数学中“系统化”程序的概念，这是希尔伯特整个方法论体系的核心概念。我们每个人在学校里学过的长乘法规则就是一个典型例子，它很好地说明了数学家所谓的系统化程序的含义。系统化程序就像简单的纸笔法，任何人都可以机械地按步骤执行，而无须任何创意或真知灼见。类似天分或直觉的东西就再也不需要了。有经验的操作员甚至都不需要知道程序的用途，就可以准确地执行它。操作员可以按照说明书上的指示准确地执行程序，而不必了解程序的目的、运作方式和原理。实际上，这不仅仅是一个抽象的概念。在企业、政府和研究机构中，有成千上万的负责计算的人员在执行系统化的操作流程。他们所做的烦琐的数学计算工作，如今已被电子计算机取代。有趣的是，这些从事计算工作的职员本身就被称为“计算机”。只是在那个时代，计算机根本不是一台机器，而是一个人，一个能够做到死记硬背的数学文员。
纽曼和学生说，这些系统化的数学程序的基本特征是可以通过机器来执行。这在当时是一种很新颖的表达方式，纽曼的演讲激发了图灵的想象力。许多年后，纽曼回忆起图灵发明的通用图灵机，说：“我相信这一切都是源于他参加了我关于数学和逻辑基础的课程。”纽曼认为，关于机器可以执行系统化程序的提议，启发了图灵去“尝试并说明一个完美的通用计算机器意味着什么”。纽曼的演讲让图灵非常着迷，他疯狂地思考着，以至于对演讲内容的研究占据了他多年的工作生涯。奇特的是，图灵似乎很少和别人讨论自己的想法，或者告诉别人他在想什么——就连纽曼也不例外。图灵认为这是他自己的问题，他觉得没有必要去和别人讨论。
一天，在国王学院的高桌晚宴上，学院的另一位研究员理查德·布雷斯威特（Richard Braithwaite）试图让图灵介绍下他的研究工作。布雷斯威特意味深长地说自己能理解哥德尔理论的内在联系，但是他发现图灵对此毫无反应。后来布雷斯威特在一封信中写道：“图灵完全不清楚哥德尔的工作。”他还补充道：“在一定程度上，我认为是我让图灵注意到他的工作和哥德尔的工作之间的联系。”也许图灵太过沉迷于研究通用计算机，他甚至都懒得去听纽曼关于哥德尔的后续讲座了。或许这就是纽曼后来颇为尖刻地称“图灵具有性格缺陷”的一个例证，即“图灵很难借助或利用别人的工作成果，反而更喜欢自己解决问题”。哥德尔当然没有这样的“缺陷”，他毫不吝啬地赞扬了图灵在那一年里所取得的成就。哥德尔慷慨地说，图灵向他展示了“正确的视角”。利用图灵的发现，他成功地将不完备性定理的适用范围扩展到涵盖所有包含基本算术形式的数学系统中。数学中的不完备性几乎无处不在。
1936年4月底，在一番精心准备后，图灵拜访了纽曼，并给了他一份详尽的《论可计算数及其在判定问题上的应用》的论文草稿。纽曼在阅读这篇论文时一定很震惊。图灵发明了一种通用机器，这台理想化的机器由一个无限的内存（一个无限的纸带）和一个“扫描器”组成，扫描器沿着纸带来回移动，读取纸带上打印的内容，然后在纸带上进一步打印出更多的内容。在开始计算之前，机器的程序和计算所需的所有数据都已打印在纸带上。通过选取存储在纸带上的各种不同程序，操作员可以让机器执行任何“人类计算机”可以执行的过程。这就是图灵称之为“通用”机器的原因。
在那个时代，“计算机器” 特指能够执行由 “人类计算机” 完成的工作的机器。图灵把他的发明称为“通用计算机器”（universal computing machine），不久后，它被简称为“通用图灵机” （universal Turing machine）。今天，现在大量有关通用图灵机的文献中，它的名字有时会被误称为“Turning machine”或“Türing machine”，甚至是 “universal touring machine”。通用图灵机是现代计算机的架构基础，由单一硬件主板构成，通过使用存储在内存中的程序，可以轻松地处理各种迥异的任务，例如数学计算、文字处理和下棋等。
图灵致力于驳斥希尔伯特关于数学本质的权威观点，通用计算机的提出是驳斥其观点的关键一步，但也因此招致了希尔伯特的反驳。通过对通用计算机行为的推理，图灵能够证明有一些定义明确的数学问题是通用计算机无法解决的。这个结果同哥德尔的不完备性定理一样令人震惊。正如我们今天可以很清晰地表述，图灵证明了对于部分有明确定义的数学问题，即使计算机有无限的内存空间，能够永远持续计算，在有穷的步骤内也无法给出“是”或者“否”的答案。充满干劲的计算机程序员有时认为，只要问题表述得足够精确，能够写出合适的程序，计算机就能解决任何数学问题，但是图灵的结论表明，这种乐观是没有根据的。
图灵给出了几个此类定义明确的数学问题作为示例，它们都是计算机在有穷步骤内无法解决的。其中之一就是打印难题，即针对任意一个给定的图灵机程序，判断运行该程序后是否一定会在纸带上打印“0”。许多程序会在某个时刻打印出0，而有些程序则永远不会。从原理上讲，即使不运行图灵机，只要对程序的性质进行推理，应该是可以做出判断的。只要证明经过有限步数的推理，我们就可以给出“是”或“否”的明确答案，而且更进一步，不管对哪个图灵机程序执行推演，我们都应该可以给出明确的答案。如果完成上述两点的证明，那就解决了打印难题。显然，没有一台计算机可以解决这个看起来很简单的问题。
哥德尔和图灵给希尔伯特关于数学本质的观点带来了双重打击，并且从此再也没有恢复。哥德尔的不完备性结论第一次打击了希尔伯特关于数学本质上可证明的观点。5年之后，图灵彻底推翻了希尔伯特摇摇欲坠的宝座。哥德尔的打击集中在一个非常具体的系统算术规则上，而图灵使用通用机器作为武器，在更普遍的范围进行了反驳。基于图灵机能够执行任何系统化程序这一事实——如今我们简称其为“图灵论题”，图灵能够得出比哥德尔更普适的结论。图灵开发了重绘数学蓝图所需的工具，精确指出了与打印难题类似的一些数学问题，是无法通过任何系统化的程序来解决的。
希尔伯特认为，一定存在一个最高阶的系统程序，可以用来确定数学中的真假。纽曼嘲讽地称这个系统程序为“新的魔法石”，暗指能够帮助炼金术士把铅变成黄金的神秘物质。有了这个神奇的系统程序后，任何人不需要任何见识、直觉或创意，都能分辨出任意给定的数学命题是对还是错。希尔伯特说，为了把整个数学体系建立在“人人都认同的具体基础上”，就必须存在一个最高阶的系统程序。哥德尔的工作动摇了人们对存在最高阶系统程序的信念，现在图灵又提出了一个完全令人信服的论点，那就是不存在最高阶程序。如果这个程序确实存在，那么通用图灵机就可以实现它，因为通用图灵机可以执行所有系统程序。有了这个“新的魔法石”，通用图灵机就能解决所有“是”或“否”的问题。然而，图灵已经明确地证明，通用图灵机不能解决所有“是”或“否”的问题。毋庸置疑，希尔伯特的最高阶系统程序不可能存在。
尽管当时对图灵来说，纠正希尔伯特谬误的工作很重要，但从今天的角度看，这与他发明精妙的通用计算机相比，真的是不值一提。图灵从一开始就对制造通用计算机产生了浓厚兴趣，但他并不了解合适的制造技术。在维多利亚时代，颇具远见的查尔斯·巴贝奇曾经梦想建造一台巨大的通用数字计算机，他称之为“引擎”，可以接管数百个“人类计算机”的工作（如图）。如果图灵是现代计算机之父，那么巴贝奇无疑就是其祖父。巴贝奇在去世前完成了雄心勃勃的“引擎”机的雏形设计，但是他从来没有制造出完整的机器来。根据巴贝奇的设计，机器读取的指令打印在与色带相连的卡片上——这个想法是巴贝奇从自动提花织布机上借鉴来的。
“分析引擎”的设计初衷，虽然考虑了把数据存储在其内存（巴贝奇将其简单地称为“存储器”）中，但是并没有考虑指令本身的存储。巴贝奇的机器缺少现代计算机的基本特征，即图灵的存储程序设置。由于巴贝奇生活在维多利亚铁路时代，所以他打算利用铁路发动机和其他工业机械使用的零部件，如黄铜齿轮、棒、棘轮、小齿轮等，来实现建造计算引擎的计划。
巴贝奇1号差分机，1824-1832年。丨图片来源：Science Museum / SSPL
采用类似巴贝奇的机械部件，当时人们成功地制造出了小型专用计算机。1931年，麻省理工学院研制的模拟微分分析器（Differential Analyser）就是其中之一。该计算机需要一个熟练的技工使用铅锤来为每项新任务“编程”！不过，巴贝奇“蒸汽铁路时代”的技术对图灵来说毫无用处。图灵需要可以支持高速运行的技术，做到能够将指令和数据存储在一个相当紧凑的空间里，而机械齿轮无法胜任。
1936年，机电式继电器成为制造电子信息处理设备（如电话交换机和穿孔卡片分拣设备）的主要技术。它是一个小型的电动开关，由电磁铁和弹簧推动的金属棒组成。当金属棒朝一个方向移动时，就可以联通电路，当金属棒朝相反方向弹回来时，电路就会断开。继电器体积大，速度慢，还笨重，而且可靠性也差。图灵开玩笑说，一台由继电器制成的通用图灵机，需要有伦敦市中心的阿尔伯特音乐厅那么大的空间才放得下。直到第二次世界大战期间，图灵和纽曼同在布莱切利庄园从事密码破译工作，他们才了解到如何制造通用图灵机。秘诀就是电子管，英国人叫电子管，美国人则称其为真空管。因为电子管中唯一运转的部分是电子束，所以它的运行速度比继电器快很多倍。这两位密码破译者的梦想就是建造一台高速的通用电子计算机。
纽曼曾在圣约翰学院讲授过这个棘手的问题，图灵在他的研究中也直面了这个难题。1939年，哥德尔在访问距离芝加哥两小时车程的圣母大学时做了一些逻辑导论的讲座，并对图灵关于判定问题的看法进行了生动的描述。哥德尔提到了一个想象中带有曲柄的机器。这台机器有点儿像打字机，可以在其中键入数学公式。输入一个可以用所谓的“命题演算”（非常简单的基础数学）概念来表示的公式，然后转动曲柄一次，如果在命题演算中公式能被证明，则机器会响铃，如果该公式无法被证明，则不会响铃。也就是说，机器能够“决定”这个公式是否可证明。图灵对判定问题的研究显示，如果公式无法用简单的命题演算的形式来表示，那么就不可能建立一台计算机在有穷步骤内来确定公式是否可证明。这是对希尔伯特观点的又一个致命打击，因为希尔伯特和他的支持者相信，应该存在一个最高阶系统程序来决定所有的数学问题。最后，哥德尔补充说，图灵的研究结果表明，“人类的思维永远无法被机器所取代”——这是我将在本书第十一章中说到的有趣观点。
就在图灵准备把他的手稿寄给一家期刊的编辑时，美国逻辑学家阿隆佐·丘奇（Alonzo Church）发表的论文的副本也送到了剑桥。丘奇比图灵大几岁，是普林斯顿大学数学系的一名年轻的土耳其人。20世纪20年代末，他在哥廷根大学与希尔伯特小组一起花了近6个月的时间进行研究。仔细阅读丘奇著写的由数学符号组成的简单的两页论文，会发现其关于判定问题的研究成果与图灵的研究内容基本一致。这可能是研究人员最不想遭遇的窘态之一。是的，丘奇的论文虽然没有包含通用图灵机和存储程序的概念，但内容与图灵的手稿有明显的重合，根据学术规则，一旦有人率先发表了一个数学成果，除非其他人的论文有一些重要的不同或全新的见解，否则不得再次署名发表。幸亏有纽曼在图灵身边给他出谋划策。纽曼很清楚，图灵论文的意义远不止狭隘地应用于解决判定问题。他仍然建议图灵发表论文，甚至亲自给伦敦数学学会的编辑写信，声明即使丘奇的成果发表在先，也不应阻止图灵的作品在协会期刊上发表。和往常一样，纽曼又一次占了上风，图灵的代表作于1936年年底正式发表。
丘奇的方法并没有说服哥德尔，哥德尔发现了论文中有争议的漏洞。丘奇关于无法构建决策机器的证明并不能让人信服。哥德尔那个假想的带有曲柄的机器就很形象。直言不讳是学者的典型特征，哥德尔率直地告诉丘奇，他的技术方法“完全不能令人满意”（丘奇在某封信件中提及）。但是当哥德尔读到图灵的论文时，他发现图灵成功地弥补了丘奇的漏洞。哥德尔赞赏地写道，图灵的“机械可计算性的定义”是“最令人满意的”，而且将事实“毫无争议”地展现了出来。
图灵的论文中也存在一些小错误。不过，相比整篇复杂的数学论文而言，这些小错误都是很浅显的，主要是图灵粗心大意所致。几个月后，图灵发表了一篇修订版论文，但其中仍有一些小纰漏未被发现。第二次世界大战后，图灵在英国国家物理实验室的年轻助手唐纳德·戴维斯（Donald Davies）发现了这些错误——戴维斯称之为“粗心的编程错误”。年轻的戴维斯天真地认为图灵在听到他所发现的错误时会很欣慰。戴维斯回忆道：“我跑去告诉他，当时我非常高兴。”然而，图灵生气了。“他非常生气，”戴维斯平静地回忆说，“他愤怒地指出这些疏忽并不重要，本质上来说这结论是对的。”图灵的家人很清楚图灵的这个性格特点，他的母亲指出：“真正让图灵生气的是与他在科学观点上的矛盾。”有时他不得不离开房间，来摆脱糟糕的坏心情。
论文发表后，图灵是时候展翅高飞了。他选择前往数学和科学蓬勃发展的新国度——美国。从1935年起，图灵就一直想去普林斯顿大学访学，现在他知道了丘奇的存在，去那里就显得更有意义了。普林斯顿大学位于新泽西州南部不断蔓延的城市边缘，有着新哥特式的石头建筑和四合院，就像一个梦幻般的绿洲，是这个地球上最伟大的数学家居住的“温室世界”。图灵马上就有机会能够与丘奇一起合作进行数学研究了。丘奇很了解图灵，后来也是他率先使用“图灵机”一词来指代图灵的发明成果的。图灵收拾好行囊，离开了与世无争的剑桥。
本文经授权节选自《图灵传：智能时代的拓荒者》（中信出版社，2022年10月版），图片为编辑所加。
相关阅读
3 图灵奖得主Pearl：期待一场迷你革命，让机器理解“为什么”
5 计算机不是只会 “计算”，图灵机也不是一台“机器” | AI那厮
近期推荐
3 有效性可疑，安全性堪忧，抗新冠口服药阿兹夫定是怎么上市的？
4 诺奖得主深陷论文图片造假漩涡，合理的图片处理应符合什么规则？
特 别 提 示
1. 进入『返朴』微信公众号底部菜单“精品专栏“，可查阅不同主题系列科普文章。
2. 『返朴』提供按月检索文章功能。关注公众号，回复四位数组成的年份+月份，如“1903”，可获取2019年3月的文章索引，以此类推。
版权说明：欢迎个人转发，任何形式的媒体或机构未经授权，不得转载和摘编。转载授权请在「返朴」微信公众号内联系后台。
长按下方图片关注「返朴」，查看更多历史文章